Generally, there is a technique called an optimal area finding technique that is used, for example, for finding a region having the highest power consumption from a map, finding a region that is congested with cars from a map, or the like. The technique is implemented by solving an optimal area finding problem of “outputting an area having a maximum score when scores calculated based on evaluation values are defined for a set of point data having two-dimensional coordinates and the evaluation values.
Here, an example of a conventional technique for solving the optimal area finding problem will be described. FIG. 31 is a diagram illustrating the conventional technique. The two-dimensional coordinates illustrated in FIG. 31 represent a coordinate system in which the horizontal direction is set as the x axis, and the vertical direction is set as the y axis. Each point distributed on the two-dimensional coordinates has its evaluation value v. In other words, the point data is represented by (x, y, v). In the example illustrated in FIG. 31, each white dot (open circle) is a point of v=1, and each black dot (filled circle) is a point of v=−1.
In the example illustrated in FIG. 31, a case will be described in which an area, in which the sum of the evaluation values v of the points is the maximum, is to be found from an area R including a set of the points. For example, according to a conventional technique, two segments that pass through the points and are parallel to the x axis and two segments that pass through the points and are parallel to the y axis are selected. Then, rectangular areas surrounded by these four segments are listed, and the score of each rectangular area, that is, the sum of the evaluation values v of the points in each rectangular area is calculated. Then, by selecting the rectangular area for which the calculated score is the maximum, an optical area r is found from the area R.
David P. Dobkin, Dimitrios Gunopulos, Wolfgang Maass: Computing the Maximum Bichromatic Discrepancy with Applications to Computer Graphics and Machine Learning. J. Comput. Syst. Sci. 52(3): 453 to 470 (1996) is an example of the conventional technique.